In certain video or film image processing systems, the image rate (number of images per second) is insufficient for high-quality display. Consequently, additional images are generated via an interpolation function and displayed between original images in order to increase the image rate and improve the quality of the display. An interpolation function of this type conventionally calculates the value of the pixels of an interpolated image, in particular as a function of the value of the pixels of the preceding original image and/or the value of the pixels of the following original image.
Such an interpolation function is based on the correlation that exists between successive images of a video or film. This is because, in a sequence of video images, subjects that are moving generally appear in different respective regions of several consecutive images. Interpolated images are therefore generated from parts of preceding and/or following original images.
Conventionally, an image is divided into pixel blocks and the assumption is made that each block is substantially identical from one image to another even if there is motion of this block between two images. Consequently, an image is interpolated from original images by seeking, for each current block of the image being interpolated, that one of the blocks of a preceding original image and/or a following original image that is the most probable.
Motion estimation and/or compensation methods offer block searching methods thus adapted for generating interpolated images. A correlation between those parts of the consecutive images in which a moving object appears may in fact be expressed via a motion vector. The motion vector represents the motion of a pixel block from one image to the other. It has a vertical component and a horizontal component, representing the displacement that has to be applied to a block of a preceding image in order to arrive at the position of a substantially identical pixel block in a following image.
Such methods are conventionally used in video data compression systems, such as systems based on the MPEG standard. Such systems are used to reduce the quantity of image data to be transmitted or stored, by compressing this data so as to allow it to be rapidly transferred to digital networks or even telephone lines, or to allow it to be recorded on digital media. Consequently, only certain reference images are encoded and transmitted, and then, on the receive side, the missing intermediate images are interpolated according to the motion vectors transmitted with the encoded images.
In such systems, on the transmit side, the intermediate image is processed so as to transmit the least possible amount of information, as mentioned above. Thus, the intermediate image is divided into blocks. For each block, a correlation is calculated between the current block and a selection of candidate blocks of a preceding and/or following original or already processed image. This correlation calculation delivers an error relating to each candidate block. A candidate block is elected, in order to represent the current block of the intermediate image. The elected candidate block is that one having the highest correlation with the current block, or else the smallest error. To allow interpolation of the intermediate images on the receive side, the processed image is transmitted via the following information, which is generally transmitted relative to a current block of an image to be interpolated:                an indication of the candidate block elected;        a motion vector representing a displacement of the elected candidate block to the position of the current block; and        an error delivered by the correlation calculation.        
Thus, on the receive side, the missing processed images are interpolated on the basis of the information received with the encoded images and a value of pixels of each block of these images is thus determined.
Certain interlaced image display systems also use motion estimation and/or compensation methods.
Image rate conversion devices also employ such methods. Such devices make it possible in fact to increase an original image rate by generating additional images obtained by interpolation of the original images. These devices are conventionally used to adapt the image rates between, on the one hand, an image generation, encoding, transmission and/or storage system and, on the other hand, an image display system, which involve different image rates.
In this case, the image to be interpolated is divided into blocks. For each of the blocks, candidate vectors are generally generated. For each of the candidate vectors, a block in the preceding original image and a block in the following original image corresponding to a displacement of the position of the current block relative to the candidate vector are selected, and then the correlation between the selected block of the preceding image and the selected block of the following image is calculated. The candidate vector elected is the vector for which the calculated correlation is the largest. The current block is then interpolated from the block in the preceding original image and from the block in the following original image that are associated with the candidate vector elected. In this way, images are generated by interpolation.
The term “processed image” refers to images divided into a plurality of blocks for which a motion vector has been elected. Thus, interpolated images are generated by interpolation of the processed images.
The next section presents basic concepts conventionally used in motion estimation methods. It is common practice to distinguish several types of images: original images of type I (intra images) which are encoded without reference to other images; images of type P (predictive images) which are interpolated via a motion estimation algorithm on the basis of a preceding original image; and images of type B (bidirectional images) which are interpolated via a motion estimation algorithm based on a preceding original image and on a following original image.
As described above, a motion estimation is based on the assumption that a pixel block of the image being processed can be modeled as displacement of a block of the preceding and/or following original image. Consequently, each current block of the image being processed is normally generated from a block of the preceding and/or following original image. It is therefore supposed that each pixel of any one block undergoes substantially the same displacement. The motion vectors represent this displacement information. Consequently, a motion vector is associated with each of the blocks of a processed image and consequently, by applying, to the blocks of the preceding original image and/or to the blocks of the following original image, a displacement corresponding to the respective associated motion vectors, an interpolated image is obtained.
One difficulty with such methods is how to search, in each of the blocks of a current image to be interpolated, for the block(s) of the preceding and/or following image that is (are) best suited among a set of candidate blocks. For this purpose, motion estimation methods are conventionally based on block matching techniques in which a motion vector is obtained by reduction of a cost function that measures the difference between the matched blocks.
For each given block of the image being processed, a motion search technique is carried out in order to determine where this block is in the preceding original image and/or the following original image. The most appropriate of the blocks of the preceding and/or following image is then elected. This is based on the assumption that each block is substantially identical from one image to another, as was mentioned above.
Thus, there is known a technique based on a full search algorithm in which a set of blocks is selected from the preceding original image and/or from the following original image that lie within a window of determined dimensions centered on the block, this being called the search window. A correlation is calculated for each of the blocks of the search window for the preceding and/or following original image. The block giving the best correlation (or else the smallest error) is selected.
FIG. 1 illustrates such a search applied to a search window whose dimensions are 8 blocks by 4 blocks.
A major drawback of this technique is the number of calculations to be performed, this being larger the larger the size of the search window.
Other search techniques provide a motion estimation according to information associated with the blocks of a preceding processed image and/or with the blocks of the image being processed, so as to estimate the motion of each of the current blocks of the image being processed. In this type of method, a motion vector is associated with each of the blocks of the processed images and these motion vectors are stored in order to be used when processing the following image to be processed.
For this purpose, two types of motion vectors are conventionally defined:                spatial motion vectors representing a spatial correlation (that is to say representing the motion of adjacent blocks in the image being processed); and        temporal motion vectors representing a temporal correlation (that is to say representing the motion of any blocks in the preceding processed image).        
Methods offering a reduction in the quantity of calculations relating to the search for suitable blocks for the processing of an image by selecting candidate motion vectors from within a search window are known. The correlation calculation is performed only for these selected candidate vectors. Thus, by limiting the number of candidate motion vectors, the number of correlation calculations needed is reduced. Consequently, the election of a motion vector for a current block of an image being processed is less costly.
Certain methods offer a selection of candidate motion vectors based on a criterion associated with the relative position of blocks of the preceding processed image relative to the position of the current block in the image being processed. Thus, candidate motion vectors are selected only if they are associated with blocks deemed to be relevant owing to their position.
Moreover, the motion of a block is considered to be substantially equivalent to the motion of a neighboring block. In general, therefore, spatial candidate motion vectors, that is to say motion vectors that have already been associated with neighboring pixel blocks in the image being processed, are also selected.
With this type of method there is a risk of selecting a set of candidate vectors that are not relevant to a given current block and consequently of electing a motion vector from a set of candidate motion vectors that may not be relevant to a current block. This is because the selection of the candidate motion vectors is carried out according to a fixed rule associated with the position of the blocks relative to the current block. It is therefore carried out independently of the actual relevance of the blocks with respect to the current block.
FIGS. 2a and 2b illustrate a selection of candidate motion vectors of this type. The candidate motion vectors are selected from within a search window around a current block 201 of an image 200 being processed (FIG. 2a). The corresponding search window in the preceding processed image bears the reference 206 (FIG. 2b). Candidate blocks of the current block 201 are selected on the basis of their relative position with respect to the current block. Thus, the blocks 202, 203, 204 and 205 of the current processed image and the blocks 207, 208, 209, 210 and 211 of the preceding processed image are selected. The selected candidate motion vectors of the current block 201 are consequently the motion vectors V1, V2, V3, V4, V5, V6, V7, V8 and V9 associated with the blocks 202, 203, 204, 205, 207, 208, 209, 210 and 211, respectively.
The selection of candidate vectors obeys a fixed rule. Under such circumstances, the selection results in relatively poor performance, especially when the current pixel block corresponds in the image being processed to the boundary of a moving object.
Specifically, the performance of motion estimation and/or compensation devices is greatly dependent on the quality of the selection of the candidate motion vectors. This is because an effective selection of candidate motion vectors makes it possible to reduce the number of correlation calculations, which is equal to the number of candidate motion vectors selected. Consequently, it is desirable to have a method of selecting candidate vectors that is efficient. From another standpoint, this selection must be accomplished by selection rules that remain simple.